<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
  <!-- k个数相加等于n的数(数字不能重复)

```
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
 
  示例 1:
  输入: k = 3, n = 7
  输出: [[1,2,4]]
  解释:
  1 + 2 + 4 = 7
  没有其他符合的组合了。

  示例 2:
  输入: k = 3, n = 9
  输出: [[1,2,6], [1,3,5], [2,3,4]]
  解释:
  1 + 2 + 6 = 9
  1 + 3 + 5 = 9
  2 + 3 + 4 = 9
  没有其他符合的组合了。

  示例 3:
  输入: k = 4, n = 1
  输出: []
  解释: 不存在有效的组合。
  在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
```
 -->
</head>
<body>
  <script>
  var combinationSum3 = function(k, n) {
    let res = []
    function helper(sum, target, paths, start) {
        if (sum === target) {
            // 结果数字个数等于 k 个，入选结果
            if (paths.length === k) res.push(paths)
            return
        }
        // 选择范围 9 个数
        for (let i=start; i<=9; i++) {
            // 结果数字个数大于 k 个跳过
            if (paths.length > k) break
            
            // 剪枝
            if (target - sum >= i) {
                helper(sum+i, target, [...paths, i], i+1) // i+1 去重
            }
        }
    }
    helper(0, n, [], 1)
    return res
  };
  console.log(combinationSum3(3,7));
  </script>
</body>
</html>